import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

//力扣215. 数组中的第K个最大元素
class Solution {
    public int findKthLargest(int[] nums, int k) {
        createHeap(nums);
        int heapSize = nums.length;
        for(int i=0;i<k-1;i++){
            //低效:
            // nums[0] = -10001;
            // createHeap(nums);

            swap(nums,0,heapSize-1);
            heapSize--;// 相当于移除当前的最大值
            shftDown(nums,0,heapSize);
        }
        return nums[0];
    }
    public void createHeap(int[] nums){
        //调整次数
        //nums.length-1是因为有效下标为nums.length-1，再-1是因为 满二叉树 最后一层的叶子结点 是 全部结点的个数的一半 +1
        for(int parent=(nums.length-1-1)/2;parent>=0;parent--){
            shftDown(nums,parent,nums.length);
        }
    }
    public void shftDown(int[] nums,int parent,int useSize){
        //左孩子
        int child = parent*2+1;
        while(child<useSize){
            if(child+1<useSize&&nums[child+1]>nums[child]){
                child = child+1;
            }
            if(nums[child]>nums[parent]){
                swap(nums,child,parent);
                parent = child;
                child = parent*2+1;
            }else{
                break;
            }
        }
    }
    public void swap(int[] nums,int child,int parent){
        int temp = nums[child];
        nums[child] = nums[parent];
        nums[parent] = temp;
    }


//力扣347. 前 K 个高频元素
    class Solution1 {
        //Map.Entry<K,V>是Map内部实现的⽤来存放<key,value>键值对映射关系的内部类
        public int[] topKFrequent(int[] nums, int k) {
            HashMap<Integer,Integer> map = new HashMap<>();
            int numsSize = nums.length;
            for(int i=0;i<nums.length;i++){
                map.put(nums[i],map.getOrDefault(nums[i],0)+1);
            }

            PriorityQueue<Map.Entry<Integer,Integer>> queue = new PriorityQueue<>((a, b)->{
                return a.getValue()-b.getValue();
            });

            for(Map.Entry<Integer,Integer> entry:map.entrySet()){
                queue.offer(entry);
                if(queue.size()>k){
                    queue.poll();
                }
            }

            int[] ans = new int[k];
            int flag=0;
            while(!queue.isEmpty()){
                ans[flag++] = queue.poll().getKey();
            }
            return ans;
        }
    }
}